Міністерство освіти та науки України
Національний університет “Львівська політехніка”
Інститут прикладної математики
і фундаментальних наук
Кафедра прикладної математики
Лабораторна робота № 1
“Елементи теорії множин”
Тема: множини та операції над ними.
Мета: навчитись оперувати множинами, виконувати над ними операції задопомогою засобів ЕОМ.
Теоретичні відомості:
Множини є основними об’єктами вивчення у дискретній математиці. Множина – це невпорядкована сукупність об’єктів, які називають елементами множини. Елементами можна вважати довільні об’єкти, які можуть бути названі або означені задопомогою правила, що задає належність до множин.
Множину можна зберігати в пам’яті як масив. Типові операції над множинами – об’єднання, перетин, перевірка приналежності елемента множині – реалізуються з допомогою засобів алгоритмічної мови або процедур обробки масивів (в мові Паскаль передбачені дані типу множина (SET) та дії над ними).
Нехай задані дві множини X і Y. Побудуємо всі можливі пари (x, y) такі, що x(X, y(Y. Отримана таким шляхом множина пар називається прямим добутком множин X і Y і позначається X(Y. Будь-яка підмножина множини X(Y називається відношенням R на X(Y. Якщо (x, y) (R, то будемо говорити, що “x знаходиться у відношенні R до y” і записують xRy.
Відношення R ( A(A називається транзитивним, якщо з xRy і yRz випливає xRz для всіх x, y, z ( A.
k-ту степінь відношення R на множині A можна задати рекурсивно.
ab тоді і тільки тоді, коли aRb.
ab для k>1 тоді і тільки тоді, коли існує c(A таке, що aRc і cb для a, b(A.
Відношення - називається транзитивним: ab тоді і тільки тоді, якщо знайдеться таке k, що ab для a і b, які належать даній множині.
Відношення називається транзитивним замиканням відношення R на множині A.
Для знаходження матриці транзитивного замикання відношення R на множині A зі скінченою кількістю елементів можна скористуватиси формулою:
де M – матриця, що задає відношення R на множині A, яка мітить n елементів.
Завдання:
10. Побудувати процедуру обчислення матриці транзитивного замикання.
Код програми(С++):
#include <iostream>
#define m
using namespace std;
void In_Matrix(int A[m][m], int n);
void Out_Matrix(int A[m][m], int n);
void Null_Matrix(int A[m][m]);
void Multiply_Matrix(int A[m][m], int B[m][m], int C[m][m]);
void Pow_Matrix(int A[m][m], int As[m][m], int s);
void Union_Matrix(int A[m][m], int B[m][m], int C[m][m]);
void Transitive_Matrix(int A[m][m], int B[m][m], int n);
void main()
{
int n, M[m][m], Mt[m][m];
cout<<"Ob4uslennja matruci tranzutuvnogo zamukannnja vidnowennja R na mnozhuni A."<<endl;
cout<<"Vvedit' kil'kist' elementiv mnozhunu A:"<<endl;
cout<<"n = "; cin>>n;
cout<<"Vvedit' elementu matruci M, w4o zadae vidnowennja R na mnozhuni A:"<<endl;
In_Matrix(M, n);
Transitive_Matrix(M, Mt, n);
cout<<endl<<"Matrucja M:"<<endl;
Out_Matrix(M, n);
cout<<endl<<"Matrucja M+, w4o zadae tranzutuvne zamukannja vidnowennja R na mnozhuni A:"<<endl;
Out_Matrix(Mt, n);
}
void In_Matrix(int A[m][m], int n)
{
Null_Matrix(A);
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
{
cout<<"M["<<i + 1<<","<<j + 1<<"] = ";
go: cin>>A[i][j];
if ((A[i][j] != 0)&&(A[i][j] != 1))
{
cout<<"Elementu matruci - luwe nyli abo odunuci!"<<endl;
goto go;
}
}
}
void Out_Matrix(int A[m][m], int n)
{
for(int i = 0; i < n; i++)
{
cout<<endl<<endl;
for(int j = 0; j < n; j++)
cout<<A[i][j]<<"\t";
}
cout<<endl;
}
void Null_Matrix(int A[m][m])
{
for(int i = 0; i < m; i++)
for(int j = 0; j < m; j++)
{
A[i][j] = 0;
}
}
void Multiply_Matrix(int A[m][m], int B[m][m], int C[m][m])
{
for(int i = 0; i < m; i++)
for(int j = 0; j < m; j++)
{
C[i][j] = 0;
for(int k = 0; k < m; k++)
C[i][j] += (A[i][k] * B[k][j]);
if (C[i][j] != 0) C[i][j] = 1;
}
}
void Pow_Matrix(int A[m][m], int As[m][m], int s)
{
int R[m][m];
for(int i = 0; i < m; i++)
for(int j = 0; j < m; j++)
...
